package com.zklh.leetcode.other.problem62;

/**
 * 动态规划实现
 */
class Solution3 implements SolutionInterface{

    @Override
    public int uniquePaths(int m, int n) {
        // 存储从起点到m下标+1,n下标+1,位置的路径数
        int[][] pathNums = new int[m][n];
        // 默认到自身路径数为1
        pathNums[0][0] = 1;
        // 初始化数组, 将在最上边和最左边的每个点的路径数置为1
        for (int i = 1; i < m; i++) {
            pathNums[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            pathNums[0][i] = 1;
        }
        int y = 0;
        int x = 0;
        // 从第二层开始在第一层的基础上计算, 一直到最后一层
        for (int i = 2; i <= m + n - 2; i++) {
            // 忽略上,左两边的路径数, 从1,i-1开始, 计算到 i-1, 1
            for (x=(i>n)?i-n+1:1; x < i && x <= m-1; x++) {
                y = i - x;
                pathNums[x][y]=pathNums[x-1][y] + pathNums[x][y-1];
            }
        }
        return pathNums[m-1][n-1];
    }

    public static void main(String[] args){
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.uniquePaths(3, 2));
    }
}
